package ext;

import java.util.*;
import org.junit.*;
import util.*;


public class EvenAndOddLink {
    
    public ListNode sortLinked(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode res1 = new ListNode(0), r1 = res1,
                 res2 = new ListNode(0), r2 = res2,
                 cur = head;
        // r1.next = head;
        // r2.next = head.next;
        while (cur != null && cur.next != null) {
            ListNode tmp = cur.next.next;
            r1.next = cur;
            r1 = r1.next;
            r2.next = cur.next;
            r1.next = null;
            r2 = r2.next;
            r2.next = null;
            cur = tmp;
        }
        r2.next = null;
        // if (cur != null) {
        //     r1.next = cur;
        // }
        r2 = res2.next;
        r1 = res1.next;

        ListNode pre = null, post = r2;
        while (post != null) {
            ListNode tmp = post.next;
            post.next = pre;
            pre = post;
            post = tmp;
        }
        
        r2 = pre;

        res1.next = r1;
        res2.next = r2;

        System.out.println(r1);
        System.out.println(r2);

        ListNode res = new ListNode(0), r = res;

        while (r1 != null && r2 != null) {
            if (r1.val <= r2.val) {
                r.next = r1;
                r1 = r1.next;
            } else {
                r.next = r2;
                r2 = r2.next;
            }
            r = r.next;
        }

        if (r1 != null) {
            r.next = r1;
        } else  if (r2 != null) {
            r.next = r2;
        }

        return res.next;
    }
    
    @Test
    public void test() {
        int[] nums = new int[]{1,8,3,6,5,4,7,2};
        ListNode head = ListNode.newListNodeFromArray(nums);
        System.out.println(head);
        System.out.println(sortLinked(head));
    }

}